# Add your Python code here. E.g.
# https://python.microbit.org/v/2
from microbit import *

def make_gray(graph, x, y, oldvalue, newvalue):
    '''灰化函数,让点(x,y)所在行列，和斜线上的点为不可用，或者解除不可用状态'''
    for i in range(cols):
        if graph[x][i] == oldvalue:                                        #竖直方向设置为不可用
            graph[x][i] = newvalue 

        if graph[i][y] == oldvalue:
            graph[i][y] = newvalue                                         #横向设置为不可用

        slash(graph, x - 1, y - 1, -1, -1, oldvalue, newvalue)                 #左斜上方
        slash(graph, x + 1, y - 1, 1, -1, oldvalue, newvalue)                  #右斜上方
        slash(graph, x - 1, y + 1, -1, -1, oldvalue, newvalue)                 #左斜下方
        slash(graph, x + 1, y + 1, 1, 1, oldvalue, newvalue)   

def slash(graph, x, y, x_increment, y_increment, oldvalue, newvalue):
    '''斜线方向上,graph为图数组，x为横坐标，y为纵坐标，x_increment为x方向增量，
        y_increment为y方向增量，oldvalue为老的值，newvalue为新设的值'''
    xx = x 
    yy = y
    while -1 < xx < rows and -1 < yy < cols:
        if graph[xx][yy] == oldvalue:
            graph[xx][yy] = newvalue

        xx += x_increment
        yy += y_increment
        
def pop_row_and_col(graph, rows, cols):        
    global result
    while True:
        if len(result) == 0:
            return -1, -1

        item = result.pop()
        make_gray(graph, item[0], item[1], len(result), -1)
        row_iter = item[0]
        col_iter = item[1] + 1

        while col_iter < cols:
            if  graph[row_iter][col_iter] == -1:
                return row_iter, col_iter

            col_iter += 1
           
def solving(graph):
    global result
    row_iter = 0
    col_iter = 0

    if len(result) > 0:
        row_iter, col_iter = pop_row_and_col(graph, rows, cols)
        if row_iter == -1 and col_iter == -1:
            return False

    found = False
    while True:    
        while True:
            if graph[row_iter][col_iter] == -1:
                make_gray(graph, row_iter, col_iter, -1, len(result))
                result.append((row_iter, col_iter))
                if len(result) == rows:
                    found = True
                    break

                row_iter += 1
                col_iter = 0
            else:
                col_iter += 1
                if col_iter >= cols:
                    row_iter, col_iter = pop_row_and_col(graph, rows, cols)
                    if row_iter == -1 and col_iter == -1:
                        break

        if found == False:
            row_iter, col_iter = pop_row_and_col(graph, rows, cols)
            if row_iter == -1 and col_iter == -1:
                break
        else:
            break

    return found
        
rows = 5
cols = 5

mygraph = [[-1 for col in range(cols)] for row in range(rows)]  

result = []

def on_button_pressed():
    global mygraph, result
    if solving(mygraph) == True:
        display.clear()
        for item in result:
            display.set_pixel(item[1], item[0], 5)
    else:
        result = []
        display.show(Image.HAPPY)

while True:
    if button_a.was_pressed() or button_b.was_pressed():
        on_button_pressed()

